package com.wangzemin.leetcode.num142;


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode virHead = new ListNode(-1);
        virHead.next = head;

        ListNode fastNode = virHead;
        ListNode slowNode = virHead;

        ListNode encounterNode = null;
        while (fastNode != null && slowNode != null && fastNode.next != null) {
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
            if (fastNode==slowNode){
                encounterNode = fastNode;
                break;
            }
        }
        if (encounterNode==null){
            return null;
        }
        slowNode = virHead;
        while (slowNode!=encounterNode){
            slowNode= slowNode.next;
            encounterNode = encounterNode.next;
        }

        return slowNode;
    }
}